#include "../tools.h"

// 第 k 个最大的元素，right - k + 1
int qsearch(vector<int>& arr, int left, int right, int k){
    if(left == right) return arr[left];

    int base = left;
    int p1 = left + 1, p2 = right;
    while(p1 < p2){ // p1 == p2 停
        while(p1 < p2 && arr[base] <= arr[p2]) --p2;
        while(p1 < p2 && arr[p1] <= arr[base]) ++p1;
        if(p1 < p2) swap(arr[p1], arr[p2]);
    }
    if(arr[p1] < arr[base]) { // !
        swap(arr[p1], arr[base]);
        base = p1;
    }
    cout << base << " " << left << "-" << right << endl;
    show(arr);

    if(base == k) return arr[base];
    if(base < k) return qsearch(arr, base + 1, right, k);
    else return qsearch(arr, left, base - 1, k);
}

int main(int argc, char const *argv[])
{
    // vector<int> nums = {-1,0,3,3,5,9,9,9,12};
    // vector<int> nums = {6, 2, 1, 7, 9, 3, 4, 5, 10, 8};
    vector<int> nums = {7,6,5,4,3,2,1};
    int k = 2;

    cout << qsearch(nums, 0, nums.size() - 1, nums.size() - 1 - k + 1);


    return 0;
}
